package stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 84.柱状图中最大的矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */
public class largestRectangleArea {

    /**
     * hot100一刷
     * hot100二刷
     */
    public static int largestRectangleArea(int[] heights) {
        int[] h = new int[heights.length + 2];
        for (int i = 1; i < h.length - 1; i++) {
            h[i] = heights[i - 1];
        }
        Deque<Integer> q = new ArrayDeque<>();
        int max = 0;
        q.push(0);
        for (int i = 1; i < h.length; i++) {
            while (!q.isEmpty() && h[i] < h[q.peek()]) {
                int mid = q.pop();
                if (q.isEmpty())
                    break;
                max = Math.max(max, h[mid] * (i - q.peek() - 1));
            }
            q.push(i);
        }

        return max;
    }


}
